/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function (nums) {
  let nLen = nums.length,
    i = nLen - 2,
    j = nLen - 1;

  // 从右往左扫描，第一个左边小于右边的值（从个位往十位上看，能交换的值），找到i，i+1~nLen为升序排列
  while (i >= 0 && nums[i] >= nums[i + 1]) {
    i--;
  }

  // 从右往左找到第一位比i处位置大的值，和i处的值互换，保证值升的最小
  if (i >= 0) {
    while (nums[j] <= nums[i]) {
      j--;
    }
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }

  // 因为从i+1~nLen为升序排列，所以直接用双指针翻转区间
  let left = i + 1,
    right = nLen - 1;

  while (left < right) {
    [nums[left], nums[right]] = [nums[right], nums[left]];
    left++;
    right--;
  }

  console.log(nums, i);
};
